Many search tasks involve computing the inner product of a query vector with a set of database vectors to find database instances having the largest inner products (e.g., highest similarity). This is a Maximum Inner Product Search (MIPS) problem. But computation of the inner products via a linear scan requires O(nd) time and memory, which is prohibitive when the number of database vectors (n) and the dimensionality (d) is large. An inner product operation is also commonly referred to as a dot product.